package leetcode.dynamic_programming;


import java.util.Arrays;

/**
 * 343. 整数拆分
 * <p>
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * <p>
 * 示例 2:
 * <p>
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 * <p>
 * 递归树    --重叠子  -- 递归到底情况  ---自顶向下
 * <p>
 * 记忆搜索法--
 * <p>
 * 动态规划-- 自底向上
 */
public class Solution343 {
    //递归实现
    public int integerBreak(int n) {
        return breakInteger(n);
    }

    private int breakInteger(int n) {

        if (n == 1) {
            return 1;
        }
        int res = -1;

        //将n拆开  拆成  i  n-i
        for (int i = 1; i < n - 1; i++) {
            //每次拆分，求出  max(res, i* (n-i),i*breakInteger(n-i))  因为最少拆分为两部分 也就存在 i* (n-i)
            res = Math.max(res, Math.max(i * (n - 1), i * breakInteger(n - i)));
        }
        return res;
    }

    //递归实现 --加记忆搜索
    public int integerBreak2(int n) {
        int[] sum = new int[n + 1];
        Arrays.fill(sum, -1);
        return breakInteger2(n, sum);
    }

    private int breakInteger2(int n, int[] sum) {

        if (n == 1) {
            return 1;
        }
        int res = -1;
        if (sum[n] != -1)
            return sum[n];
        //将n拆开  拆成  i  n-i
        for (int i = 1; i <= n - 1; i++) {
            //每次拆分，求出  max(res, i* (n-i),i*breakInteger(n-i))  因为最少拆分为两部分 也就存在 i* (n-i)
            res = max3(res, i * (n - i), i * (breakInteger2(n - 1, sum)));

        }
        sum[n] = res;
        return res;
    }

    private int max3(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    /**
     * 使用动态规划 进行自底向上解决；
     *
     * @param n
     * @return
     */
    private int breakInteger3(int n) {

        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);//初始化为-1

        memo[1] = 1;//对于一个数，进行拆分 1- (n-1)  对应另一半 (n-1) - 1
        for (int i = 2; i <= n; i++) {
            int res = -1;
            //对当前 i 进行拆分  j  i-j;
            for (int j = 1; j <= i - 1; j++) { //或者拆成了多于两个
                res = max3(res, j * (i - j), j * memo[i - j]);
            }
            memo[i] = res;
        }

        return memo[n];
    }

    public static void main(String[] args) {
        Solution343 s = new Solution343();
        s.breakInteger3(3);
    }
}
